在imooc上学习python进阶的时候，碰到了这样一个小题：实现一个有理数类，并添加“加减乘除”四个方法。当然这是一个很简单的小题啦，我一看到这道题的时候也是这么想的，但是后来发现这样一道小题想要解好还是不容易的。下面，我们就来看看遇到的困难和一些思考。
1
2
3
4
5
6
7
class Rational (object) :
def __init__ (self, p, q) :
self.p = p
self.q = q
def __str__ (self) :
return '%s/%s' % (self.p, self.q)
__repr__ = __str__
此时，我们就可以利用Rational(p,q)语句来生成各个有理数对象了。此时，我们的对象就已经准备就绪了，下面只要实现“加减乘除”四个方法了。我首先写的代码是下面这样的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Rational (object) :
def __init__ (self, p, q) :
self.p = p
self.q = q
def __add__ (self, r) :
return Rational(self.p * r.q + self.q * r.p, self.q * r.q)
def __sub__ (self, r) :
return Rational(self.p * r.q - self.q * r.p, self.q * r.q)
def __mul__ (self, r) :
return Rational(self.p * r.p,self.q * r.q)
def __div__ (self, r) :
return Rational(self.p * r.q,self.q * r.p)
def __str__ (self) :
return '%s/%s' % (self.p, self.q)
__repr__ = __str__
但是这样的问题就来了：正常的计算后是有约分过程的，很显然这里并没有实现这个功能，所以输出的结果肯定不是最简形式。下面我们的问题就来了，我们如何实现化简？我们很容易想到求取p，q的最大公约数，然后进行约分，这当然是最正确的方法。那么，除了遍历较小的正整数到1这种通用的方法，还有什么好的算法可以用呢？
公式表述：a>b,所以a = k*b + r，则r = a mod b。我们假设d为a和b的公约数，则有a = a1*d,b = b1*d，所以a1*d = k*b1*d + r，即r = (a1 - k*b1)d，可见r和b拥有相同的公约数，所以gcd(a,b)=gcd(b,a mod b)。如果a<b,则a = a mod b，那么恒等式gcd(a,b)=gcd(b,a)成立。gcd(a,b)=gcd(b,a mod b)。
我们有了具体的算法，就可以写程序了，下面是照着上述算法写出来的程序，利用了递归。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def gcd (a,b) :
if a % b == 0 :
return b
elif b % a == 0 :
return a
elif a > b:
return gcd(b,a % b)
else :
return gcd(a,b % a)
class Rational (object) :
def __init__ (self, p, q) :
self.p = p
self.q = q
def __add__ (self, r) :
p = self.p * r.q + self.q * r.p
q = self.q * r.q
s = gcd(p,q)
return Rational(p/s,q/s)
def __sub__ (self, r) :
p = self.p * r.q - self.q * r.p
q = self.q * r.q
s = gcd(p,q)
return Rational(p/s,q/s)
def __mul__ (self, r) :
p = self.p * r.p
q = self.q * r.q
s = gcd(p,q)
return Rational(p/s,q/s)
def __div__ (self, r) :
p = self.p * r.q
q = self.q * r.p
s = gcd(p,q)
return Rational(p/s,q/s)
def __str__ (self) :
return '%s/%s' % (self.p, self.q)
__repr__ = __str__
得到的结果很满意，应该约分的都实现了正确的约分。但是，上面说的欧几里德算法是否已经写到最精简了呢？我们都会觉得自己已经实现了功能，然后就不再关注代码了，其实还有精简的余地。我们上面的代码是在判别a，b的大小后，再进行相应的计算的，这样的方式，确实是对上面算法进行了实现，但是显得很冗余，有没有更简单的写法？
1
2
3
4
5
def gcd (a,b) :
if 0 == b:
return a
else :
return gcd(b,a%b)
上面的这种写法就要简单的多，因为上面的证明说到如果b大于a，那么gcd(a,b)=gcd(b,a mod b)=gcd(b,a)，所以后面的数总是较小的一个，如果其为0，那么很显然是a%b=0，应该返回本次的a值，即上一次的b值。a大于b的情况就是简单的公式套用了，不用多解释。
